1. Field of the Invention
The present invention relates to cryptographic algorithms and, in particular, to concepts for processing cryptographic algorithms in efficient and economical ways.
2. Description of the Related Art
In technology, a plurality of cryptographic algorithms are known, wherein certain cryptographic algorithms, such as, for example, the DES algorithm or the AES algorithm according to Rijndael, are round-based. A cryptographic algorithm working in rounds performs certain operations on bits to be encrypted in rounds, wherein the operations of a round are usually identical, wherein, however, a different round key is used in each round. Put generally, such a cryptographic algorithm includes a group of operations, wherein the operations typically include arithmetic and/or logic operations and rotation operations and/or permutation operations and/or substitution operations. In addition, such a round-based algorithm, apart from means for performing the individual operations, also requires means for flow control.
These will be illustrated subsequently referring to FIGS. 5 to 7 relating to the DES algorithm. It is to be pointed out in particular that the FIGS. 5 to 7 also relate to the double DES algorithm (2DES) or the triple DES algorithm (3DES) including a double or triple execution, respectively, of the DES algorithm.
FIG. 5 shows a device 50 for executing the DES algorithm in an encryption direction and a device 52 for executing the DES algorithm in a decryption direction (DES−1).
Plain data P is fed into the DES device 50 in blocks of 64 bits. The device 50 also receives a key K including 56 bits. On the output side, the DES device 50 provides encrypted data C. By way of analogy, the DES decrypting device 52 receives a block of encrypted data including 64 bits. The key K is again 56 bits wide so that 64 bits of plain data again result at the output of the device 52. It is to be pointed out that the DES algorithm is a symmetrical algorithm in such a way that the same key K and inverse operations can be employed when both encrypting and decrypting.
The DES algorithm is detailed in “Handbook of Applied Cryptography”, Menezes, van Oorschot, Vanstone, CRC Press, 1996, pages 252 to 260. For reasons of clarity, the principle flow of the DES algorithm will be illustrated subsequently referring to FIGS. 6 and 7. At first, 64 bits of plain text data are fed (block 60). Then, an initial permutation (IP) with the 64 bits of input data occurs. The output bits of block 61 are divided into a left half L0 including the first 32 bits and into a right half R0 including the second 32 bits (62). Subsequently, the right half R0 is fed to a round function 63, wherein the round function also receives a key K1 for the corresponding number of the round, in the present case the first round. The round function 63 provides a result which is XOR-ed with the left half of block 62 (64).
Subsequently, the left and right halves are exchanged so that the output data of the XOR linkage 64 is now treated as the right half R1 for the next round, while the input data in the function 63 is now treated as the left half L1. Then, by means of a round function 69, a processing using the key for the second round K2 is performed to subject the result of the function 64 again to an XOR linkage 64 with L1. The function 69 is identical to the function 63, except for the round key which, for the function 63, was the round key K1 and which, for the function 69, is a round key for the second round K2. This procedure is repeated, as can be seen in FIG. 6, for all the 16 rounds in order to perform again a left/right exchange in a block 66. The result of this exchange is then subjected to a final permutation 67, which in FIG. 6 is referred to as IP−1, to bring out that this permutation is the permutation inverse to the permutation of block 61.
The output of the DES algorithm (block 68) then corresponds to the encrypted data C of FIG. 5. In the case of a 2DES algorithm, the output data in block 68 is again fed into block 60 to pass the DES algorithm again, as is illustrated in FIG. 6.
In the case of the 3DES algorithm, an additional third passage takes place.
The round keys K1, K2, K3, K4, . . . , K16 are calculated from the input key K of FIG. 5 using a certain algorithm which is known in technology and includes 28-bit rotation operations and bit selection tables using a first bit selection table PC1 and a second bit selection table PC2.
FIG. 7 shows a detailed illustration of the inner function f illustrated in FIG. 6 with the blocks 63, 69. At first, an expansion operation 70 with the 32-bit input data Ri-1 takes place. The result of the expansion operation 70 is then XOR-ed (71) with the round key ki calculated for this round i. The expansion operation produces 48 bits from 32 bits, wherein certain bits of the 32 input bits are double-used to produce 48 output bits. The 48 output bits are then classified in 8×6 bits (block 72) and subjected to a bit substitution using 8 bit substitution tables, which in technology are referred to as S-BOXES, corresponding to their significance. The bit substitution tables generate 4 output bits of every 6 input bits so that 32 bits result from the 48 bits before the bit substitution (block 74). The output data of the bit substitution 73 is finally subjected to a permutation 75 to provide the result of block 63 and block 69, respectively, in a round of the DES algorithm, which is then, as is illustrated in FIG. 6 and has already been explained, subjected to an XOR linkage with the left half (block 64 or block 65).
With regard to the bit substitution 73, it is to be pointed out that the 48 bits present in block 72 are not used directly to address the S-BOXES but that a row value and a column value for the respective S-BOXES is calculated from these bits using an arithmetic linkage, with which the S-BOXES are addressed to provide 4 bit data present at the addressed location as a response to the addressing.
The permutation or expansion/permutation rules, respectively, of blocks 61, 67, 70, 75 and the bit selection rules for the key generation in the form of tables PC1 and PC2 are known in technology and are standardized for the DES algorithm. The same applies to the S-BOXES S1, S2, . . . , S8. Even the S-BOXES are standardized for the DES algorithm, and as well as the entire external flow illustrated in FIG. 6 and the round function f illustrated in FIG. 7.
Up to now, a special hardware module containing a complete implementation of the DES or 3DES algorithm, respectively, including the key generation and storage, flow control and all the operations required has been employed for speeding up the DES algorithm. This module, for reasons of safety, has been implemented as a full custom design for the largest part and is typically integrated in the design as a hard macro.
Thus, a hardware implementation of the DES algorithm results in the prior art which has an optimum speed but which is complicated with regard to the design and is also problematic with regard to the chip area requirements.
In particular in changes of the design or with an implementation of a new multi-functional cryptography processor, the hard macro must be re-processed manually and in a complicated way, which is complicated in both the design phase and in the test phase and problematic concerning the ever higher requirements to the “time to market”.
In addition, the hard macro embodiment is not optimal either with regard to the chip area requirements, particularly since flow controls for a similar cryptographic algorithms implemented on the same multi-functional cryptochip are provided individually for each algorithm, although they, in principle, perform the same functions, that is the flow control of a round-based cryptoalgorithm.
In particular, the limitation of the chip area requirements specially applying for safety ICs which are to be employed on chipcards is a considerable limitation, particularly since the circuit designer, apart from a fast DES processor, of course also desires the largest possible amount of memory so that an optimum tradeoff between chip area requirements for the memory and chip area requirements for special modules, such as, for example, the DES module, must be made.
On the other hand, it is not of utmost importance for special applications that the algorithm is processed with maximum speed. It is true that a certain speed is required, but in some cases not the maximum speed possible obtained by a complete hardware design of the DES algorithm.